package cn.zifangsky.heap.questions;

import org.apache.commons.io.FileUtils;
import org.junit.Test;

import java.io.File;
import java.io.IOException;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 文本有200亿行数据（10G大小），每行都是数字，请用java程序统计出最大的100个数字。
 *
 * @author zifangsky
 * @date 2020/6/9
 * @since 1.0.0
 */
public class Problem_003_Top100 {

    @Test
    public void testMethod() throws IOException {
        //前100个数字
        int topN = 100;

        //1. 读文本文件（如果内存不够，可以分成几个文件分别求Top100，最后再从这几个Top100中得到最终的Top100）
        List<String> lines = FileUtils.readLines(new File("G:/test.txt"), "UTF-8");
        Integer[] arr = lines.stream().map(Integer::valueOf).toArray(Integer[]::new);

        //2. 将所有数字都尝试往优先队列中添加
        Solution<Integer> solution = new Solution<>(topN);
        solution.addAll(arr);

        //3. 输出结果
        System.out.println(Arrays.toString(solution.toArray(new Integer[topN])));
    }

    /**
     * 实现算法
     */
    static class Solution<T extends Comparable<? super T>> {
        /**
         * 优先队列
         */
        private PriorityQueue<T> queue;
        /**
         * 前100个最大数字
         */
        private int topN;

        public Solution(int k) {
            this.topN = k;
            this.queue = new PriorityQueue<>(k);
        }

        /**
         * 添加整个数组
         */
        public void addAll(T[] arr){
            if(arr != null && arr.length > 0){
                for(T tmp : arr){
                    this.add(tmp);
                }
            }
        }

        /**
         * 添加一个数
         */
        public void add(T data){
            if(data == null){
                return;
            }

            //1. 如果当前队列中数量不足 topN 个，则直接插入
            if(queue.size() < topN){
                queue.add(data);
                return;
            }

            //2. 判断当前值是否比队列头结点还要小
            T head = queue.peek();
            if(data.compareTo(head) <= 0){
                return;
            }

            //3. 否则踢出队列的头结点
            queue.poll();
            queue.add(data);
        }

        /**
         * 返回最终 Top100 的数字
         */
        public T[] toArray(T[] arr){
            return queue.toArray(arr);
        }
    }
}
